package day24;

// 最大福利（核心代码模式）
// 6*6 只能向下or向右走 【从0,0 走到 5,5】

public class Main1 {

    /* 错误！会小于
    public static int getMost(int[][] board) {
        // write code here
        int max = board[0][0];  // 左上角出发
        int i = 0;
        int j = 0;
        while (i < 6-1){
            while (j < 6-1){
                // 要判断i是否还满足要求
                if(i<6-1) {
                    // 要么向右走，要么向下走
                    if(max+board[i][j+1] > max+board[i+1][j]) {
                        // 此时说明向右走最划算
                        max += board[i][j+1];
                        j++;
                    } else {
                        // 说明向下走最好！
                        max += board[i+1][j];
                        i++;
                    }
                } else {
                    // 说明此时 i==5
                    // 只能向右走到5,5位置
                    max += board[i][j+1];
                    j++;
                }
            }
            // 说明此时j==5
            // 只能向下走
            max += board[i+1][j];
            i++;
        }
        return max;
    }*/


    // 参考：
    // 一定要进行元素的更新才能知道最终结果，不能只是看临近的两个元素！！
    public static int getMost1(int[][] board) {
        // write code here
        if(board == null || board.length == 0 || board[0].length == 0)
            return -1;
        int row = board.length;
        int col = board[0].length;
        // 先计算首行首列的值，更新各值为其前一个或上一个+本身（因为只能右/下走）
        for(int i = 1;i<row;i++)
            board[i][0] += board[i-1][0];
        for(int j = 1;j<col;j++)
            board[0][j] += board[0][j-1];

        // 计算并更新每个元素（其上or左+本身）
        for(int i = 1;i<row;i++){
            for(int j = 1;j< col;j++){
                // 计算好左边和上边元素已经更新好的值就行！
                board[i][j] += Math.max(board[i][j-1] ,board[i-1][j]);
            }
        }
        // 最后更新出来的右下角就是！
        return board[row-1][col-1];
    }

    public static void main(String[] args) {
        int[][] board = {{564 ,448 ,654 ,186 ,490 ,699},
                {487 ,444 ,563 ,228 ,365 ,261},
                {429 ,505 ,612 ,564 ,715 ,726},
                {464 ,617 ,234 ,647 ,702 ,263},
                {245 ,249 ,231 ,462 ,453 ,646},
                {669 ,510 ,492 ,512 ,622 ,135}};

        int most = getMost1(board);
        System.out.println(most);
    }
}
